package mo.daliy;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class L1235 {

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        List<int[]> jobs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            jobs.add(new int[]{startTime[i], endTime[i], profit[i]});
        }

        jobs.sort(Comparator.comparingInt(o -> o[1]));

        List<int[]> dp = new ArrayList<>();
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int cur = ret;
            cur = Math.max(cur, getLastMaxProfit(dp, jobs.get(i)[0])+jobs.get(i)[2]);
            dp.add(new int[]{jobs.get(i)[1], cur});
            ret = cur;
        }

        return ret;
    }

    private int getLastMaxProfit(List<int[]> dp, int start) {
        int left =  0;
        int right = dp.size() - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            int val = dp.get(mid)[0];
            if (val <= start) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        if (dp.get(left)[0] > start) {
            return 0;
        }
        return dp.get(left)[1];
    }

}
